//约瑟夫环
//用循环列表解决约瑟夫环问题
//思路：首先要有一个指针指向当前节点，初始化完成后，this.currNode=this.head;
// 循环M次，this.currNode=this/currNode.next;然后删除当前节点，接着遍历，知道链表长度小于M，z
//注意当this.currNode.next="head"  要跳两次
function Node(element){
    this.element=element;
    this.next=null;
}

function circleList() {
    this.head = new Node("head");
    this.head.next = this.head;
    this.find = find;
    this.insert = insert;
    this.display = display;
    this.findPrevious = findPrevious;
    this.remove = remove;
    this.advance=advance;
    this.count=count;
    this.currNode=this.head;
}
//插入新节点
//先要找到你要在哪里插入，找到那个插入的点，
//先写一个find函数,先找到头结点，也就说先找到当前节点，
// 然后当当前节点的next不等于null的时候，就一直遍历，找到之后返回

function find(item){
    //这个currNode获取的是这条链表的头结点，所以你获取的是LList中的head的这个node节点
    //这个node节点有两个属性，一个next一个element
    var currNode=this.head;
    while(currNode.element!==item){
        currNode=currNode.next;
    }
    return currNode;
}

//现在开始插入
//原理：先找到这个节点，然后创建一个节点，让新节点的next指向当前节点的next值，让当前节点指向新节点
function insert(newElement,item){
    var newNode=new Node(newElement);
    var currNode=this.find(item);
    newNode.next=currNode.next;
    currNode.next=newNode;
}

//删除表中的数据
//原理：你要先找到是要删除数据的前一个节点，你要让前一个节点的next值等于要删除数据的next值，
//所以先写一个找前驱节点的函数
//找前驱和后继是一样的判断，后一个节点是否为null，且当前元素的next的值等于你要找的元素
function findPrevious(item){
    var currNode=this.head;
    while(!(currNode.next===null)&&currNode.next.element!==item){
        currNode=currNode.next;
    }
    return currNode;
}

function remove(item){
    var preNode=this.findPrevious(item);
    if(!(preNode.next===null)){
        preNode.next=preNode.next.next;
    }
}

function display(){
    var currNode=this.head;
    while(currNode.next.element!="head"&&currNode.next!=null){
        console.log(currNode.next.element);
        currNode=currNode.next;
    }
}

//向前移动n个位置
function advance(n){
    while(n>0){
       if(this.currNode.next.element=="head"){
           this.currNode=this.currNode.next.next;
       }else{
           this.currNode=this.currNode.next;
       }
       n--;
    }
}



function count(){
    var i=0;
    var node=this.head;
    while(node.next.element!="head"){
        node=node.next;
        i++;
    }
    return i;
}
var person=new circleList();
person.insert("1","head");
person.insert("2","1");
person.insert("3","2");
person.insert("4","3");
person.insert("5","4");

person.display();

var n=2;
while(person.count()>1){
    person.advance(n);
    person.remove(person.currNode.element);
    console.log("\n");
    person.display();
}
